/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
 *
 * Date: 2022-09-30
 * Time: 23:50
 */
public class Algorithm {
    /*

    // 注意 这道题目是判断 root1 是否 包含 root2
    // 与之前做过的力扣上的 root2 是不是 root1 的子树有细微的差别

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null) { return false; }

        // 判断当前的树root1是否和树root2是同一棵树
        if(isSameTree(root1,root2)) { return true; }

        // 判断当前树的左树root1.left是否和树root2是同一棵树
        if(HasSubtree(root1.left,root2)) { return true; }

        // 判断当前树的右树root1.right是否和树root2是同一棵树
        if(HasSubtree(root1.right,root2)) { return true; }

        // 代码走到这 说明root1树本身及其左右子树都不和root2相同 说明 root2 不是 root1的子树
        return false;
    }
    private boolean isSameTree(TreeNode root,TreeNode subRoot) {
        if( root == null && subRoot != null ) {
            // 一棵树为空 一棵树不为空
            return false;
        }

        if(root == null && subRoot == null || root != null && subRoot == null ) {
            // 两棵树都为空
            return true;
        }

        if(root.val != subRoot.val) { return false; }

        return isSameTree(root.left,subRoot.left) && isSameTree(root.right, subRoot.right);
    }


     */

}
